Thuật toán Dijkstra bình thường sẽ có độ phức tạp là O ( n 2 + m ) {\displaystyle O(n^{2}+m)} . Tuy nhiên ta có thể sử dụng kết hợp với cấu trúc heap, khi đó độ phức tạp sẽ là O ( ( m + n ) l o g ( n ) ) {\displaystyle O((m+n)log(n))} , nếu dùng Fibonacci Heap thì độ phức tạp giảm xuống còn O ( m + n log ⁡ n ) {\displaystyle O(m+n\log n)} . Trong đó m là số cạnh, n là số đỉnh của đồ thị đang xét.